﻿/*
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true
*/

#include "AllInc.h"

class Solution {
public:
	bool isValid(string s) {
		stack<char> record;
		int len = s.length();
		for (size_t i = 0; i < len; i++)
		{
			char c = s[i];
			if (c == ' ')
			{
				continue;
			}
			else if (c == '(' || c == '[' || c == '{')
			{
				record.push(c);
			}
			else if (c == ')' || c == ']' || c == '}')
			{
				if (record.empty())
				{
					return false;
				}
				char tmp = record.top();
				if ((tmp == '(' && c == ')')
					|| (tmp == '[' && c == ']')
					|| (tmp == '{' && c == '}') )
				{
					record.pop();
				}
				else
				{
					return false;
				}
			}
			else
			{
				return false;
			}
		}
		return record.empty();
	}
};

//int main()
//{
//	Solution s;
//	bool result = s.isValid("(])");
//
//	return 0;
//}